-- A program to perform quicksort on an array of numbers
-- 4000 = p (beggining index of array being sorted)
-- 4004 = r (end index of portion of the array being sorted)
-- 4008 = beginning of array of nums
-- 
-- R30 = SP
-- R31 = Ret Addr Reg
-- R2 = Address of beginning of array (4008)
-- R3 = p 
-- R4 = r
-- R5 = q (result of partition operation)
-- R6 = p - r for comparison
-- R7 = A[r] (x) in partition
-- R8 = i in partition
-- R9 = j in partition
-- R10 = temp in partition
-- R11 = r-j in partition used for loop comparison
-- R12 = Address of A[j]
-- R13 = Address of A[i]
-- R14 = value at A[j]
-- R15 = x - A[j] for if comparison in partition
-- R16 = Address of A[r]
-- R29 = temp reg mostly for multiplying index by 4 to get address
--
--
-- SETUP
Begin Assembly
-- Stack will be at Org5000 - R30 is SP
ADDI R30, R0, 5000
-- Load p
ADDI R2, R0, 4000
LW R3, 0(R2)
-- Load r
ADDI R2, R2, 4
LW R4, 0(R2)
-- R2 is address of beginning of array of numbers
ADDI R2, R2, 4
-- Initialize R31 to 0
ADDI R31, R0, 0
--
--
-- Quicksort algorithm
LABEL Quicksort
-- Subtract: r - p for comparison
SUB R6, R3, R4
-- Branch if greater than or equal to 0, aka p >= r
BGEZ R6, TheEnd
NOP
-- Store value of R31
SW R31, 0(R30)
ADDI R30, R30, 4
-- Run Partition
JAL Partition
NOP
-- Save values of p, r, and q
SW R3, 0(R30)
SW R4, 4(R30)
SW R5, 8(R30)
ADDI R30, R30, 12
-- Set new values for r = q-1
ADDI R4, R5, -1
-- Recursively call quicksort
JAL Quicksort
NOP
-- restore values for q, r, and p
ADDI R30, R30, -4
LW R5, 0(R30)
ADDI R30, R30, -4
LW R4, 0(R30)
ADDI R30, R30, -4
LW R3, 0(R30)
-- Set new values for p = q+1
ADDI R3, R5, 1
-- Recursively call quicksort
JAL Quicksort
NOP
-- Restore R31
ADDI R30, R30, -4
LW R31, 0(R30)
NOP
-- If p >= r TheEnd is run. Simply jump back to R31
LABEL TheEnd
BEQ R31, R0, Done
NOP
JR R31
NOP
--
--
-- Partition code
LABEL Partition
-- get the address of A[r] - store r*4 in temp reg then add the start index of the array to it
SLL R29, R4, 2
ADD R16, R29, R2
-- Load A[r] into R7 (x)
LW R7, 0(R16)
-- Set R8 (i) -> i = p-1
ADDI R8, R3, -1
-- Set j=p
ADD R9, R0, R3
-- Begin the loop in partition
LABEL PartitionLoop
-- perform r-j for comparison
SUB R11, R4, R9
-- Branch if j >= r, aka r-j <= 0
BLEZ R11, PostPartitionLoop
NOP
-- store j*4 in temp reg
SLL R29, R9, 2
-- Add the beginning of array to it to get the address of A[j]
ADD R12, R29, R2
-- Get the value of A[j]
LW R14, 0(R12)
-- Store x-A[j] for comparison
SUB R15, R7, R14
-- Branch back to the loop if A[j] > x aka x-A[j] < 0
BLTZ R15, EndLoop
NOP
-- Increment i
ADDI R8, R8, 1
-- Store i*4 in R29
SLL R29, R8, 2
-- Store complete address of A[i]
ADD R13, R29, R2
-- set temp = A[i]
LW R10, 0(R13)
-- Store A[j] in A[i]
SW R14, 0(R13)
-- Store temp in A[j]
SW R10, 0(R12)
-- Ending the Loop
LABEL EndLoop
-- increment j
ADDI R9, R9, 1
-- continue to the next loop iteration
J PartitionLoop
NOP
-- PostPartitionLoop
LABEL PostPartitionLoop
-- Store i*4 in R29
SLL R29, R8, 2
-- Store complete address of A[i]
ADD R13, R29, R2
-- Load value of A[r] into R7
LW R7, 0(R16)
-- Load temp = A[i+1]
LW R10, 4(R13)
-- Store A[r] into A[i+1]
SW R7, 4(R13)
-- Store temp in A[r]
SW R10, 0(R16)
-- Set q = i+1
ADDI R5, R8, 1
-- return
NOP
JR R31
NOP
LABEL Done
HALT
End Assembly
Begin Data 4000 48
0
10
0
23
71
33
5
93
82
34
13
111
23
End Data